package com.kevinkk.tree;

import java.util.*;

/**
 * 给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
 * 树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。
 */

public class NAryTreeLevelOrderTraversal {
    class Solution {
        public List<List<Integer>> levelOrder(Node root) {
            List<List<Integer>> res = new ArrayList<>();
            Deque<Node> que = new ArrayDeque<>();
            if(root != null) que.addLast(root);

            while(!que.isEmpty()){
                int size = que.size();
                List<Integer> row = new ArrayList<>();
                for(int i = 0; i < size; i++){
                    Node node = que.removeFirst();
                    for(int j = 0; j < node.children.size(); j++)
                        que.addLast(node.children.get(j));
                    row.add(node.val);
                }
                res.add(row);
            }

            return res;
        }
    }
}
